/*
    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
    给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

    示例:
    输入："23"
    输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <map>

using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits);

private:
    map<char, vector<const char*>> m_numMaps {
        {'2', vector<const char*>{"a", "b", "c"}},
        {'3', vector<const char*>{"d", "e", "f"}},
        {'4', vector<const char*>{"g", "h", "i"}},
        {'5', vector<const char*>{"j", "k", "l"}},
        {'6', vector<const char*>{"m", "n", "o"}},
        {'7', vector<const char*>{"p", "q", "r", "s"}},
        {'8', vector<const char*>{"t", "u", "v"}},
        {'9', vector<const char*>{"w", "x", "y", "z"}},
    };
};


vector<string> Solution::letterCombinations(string digits)
{
    deque<string> retDeq;
    for (auto c : digits)
    {
        if (retDeq.empty())
        {
            for (auto s : m_numMaps[c])
            {
                retDeq.push_back(s);
            }
        }
        else
        {   
            auto loop = retDeq.size();
            for (auto i=0; i<loop; ++i)
            {
                string tmp;
                auto iter = retDeq.begin();
                for (auto s : m_numMaps[c])
                {
                    tmp = (*iter + s);
                    retDeq.push_back(tmp);
                }
                retDeq.pop_front();
            }
        }
    }

    vector<string> sv(retDeq.begin(), retDeq.end());
    return sv;
}


int main(int argc, char *argv[])
{
    Solution obj;
    auto ret = obj.letterCombinations(argv[1]);
    cout << "ret len: " << ret.size() << endl;
    for (auto r : ret)
    {
        cout << r << "  ";
    }
    cout << endl;
}
